import java.util.Arrays;



public class KMP {
    public int[] getNext(String sub){//获取next数组
        int[] next = new  int[sub.length()];//创建next数组
        char[] s  = sub.toCharArray();
        int j = 0;
        next[0] = j;//也没前缀，也没后缀，一定为0
        for(int i=1;i<s.length;i++){
            while (j>0&&s[j]!=s[i]){//前后缀不相同的情况，如果是next[0]=-1，那么使用j时，都要进行+1操作
                j = next[j-1];//进行回退
            }
            if (s[j]==s[i]){//10行，也要进行j+1操作
                j++;
                next[i] = j;
            }
        }
        System.out.println(Arrays.toString(next));
        return next;
    }
    public int kmp(String master,String sub){//KMP算法
         int[] next = getNext(sub);
         char[] m = master.toCharArray();
         char[] s = sub.toCharArray();

         for (int i=0,j=0;i<master.length();i++){//i表示主串的位置，j表示模式串的位置
             while (j>0&&m[i]!=s[j]){
                 j = next[j-1];
             }
             if(m[i]==s[j]){
                 j++;
             }
             if(j==s.length){
                 return i-s.length+1;
             }
         }
        return -1;
    }
    public static void main(String[] args) {
        var main = new KMP();
        String sub = "aabaaf";//模式串
        String master = "aabaabaaf";
        int res = main.kmp(master,sub);
        System.out.println(res);
    }
}
